package middle;

import java.util.Arrays;
import util.PrintUtils;

public class Solution_436 {

    public int[] findRightInterval(int[][] intervals) {
        int min = 1000001, max = -1000001;
        for (int[] interval : intervals) {
            if (min > interval[0]) {
                min = interval[0];
            }
            if (max < interval[1]) {
                max = interval[1];
            }
        }

        int[] indexes = new int[max - min+2];
        Arrays.fill(indexes, -1);
        for (int i = 0; i < intervals.length; i++) {
            indexes[intervals[i][0] - min] = i;
        }
        int pre = -1;
        for (int i = indexes.length - 1; i >= 0; i--) {
            if (indexes[i] != -1) {
                pre = indexes[i];
            }
            indexes[i] = pre;
        }
        int[] arrays = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            arrays[i] = indexes[intervals[i][1] - min];
        }
        return arrays;
    }

    public static void main(String[] args) {
        Solution_436 model = new Solution_436();
        PrintUtils.arrayInt(model.findRightInterval(new int[][]{{1, 2}}));
        PrintUtils.arrayInt(model.findRightInterval(new int[][]{{3, 4}, {2, 3}, {1, 2}}));
        PrintUtils.arrayInt(model.findRightInterval(new int[][]{{1, 4}, {2, 3}, {3, 4}}));
    }
}
